'''
【问题描述】

把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的比左边大，同一

列中下边的比上边的大。一共有多少种方案？

答案很大，你只需要给出方案数除以 2020 的余数即可。
'''
dp = [[0 for _ in range(2021)] for _ in range(2021)]
dp[1][1] = 1  # 1 一定在第一行第一个
for i in range(2, 2021):  # 将第i个数放第一行
    # i代表放入的数字个数 正序放入
    for j in range(1, i + 1):
        dp[i][j] += dp[i - 1][j - 1]
        if i - j <= j:
            # 因为是正向枚举，后面的数只会越来越大 要随时保持第一行的个数不能比第二行的少 否则必然出现这一列第二行比第一行小的情况
            dp[i][j] += dp[i - 1][j]
print(dp[2020][1010] % 2020)
